package leetcode.code0794;

import leetcode.IDebug;
import leetcode.helper.HelpDebug;

/***
易错用例：

```
[[0,1,0,1,1,1,1,1,1,0],[0,0,0,1,0,0,0,0,0,0],[0,0,1,1,1,0,0,0,1,0],[0,0,0,1,1,0,0,1,1,0],[0,1,0,0,1,0,1,1,0,1],[0,0,0,1,0,1,0,1,1,1],[0,1,0,0,1,0,0,1,1,0],[0,1,0,1,0,0,0,1,1,0],[0,1,1,0,0,1,1,0,0,1],[1,0,1,1,0,1,0,1,0,1]]
```

答案是38。
算成40的，算的是添加防火墙最多。
题目要求的是`威胁最大`，也就是被威胁的0最多。
这两者并不总一致。因为邻接一个0，需要1面墙，拐角0需要2面墙，环绕0需要4面墙。这些威胁都是1。墙多并不一定是威胁大，有可能是为了保护某一个0建了更多的墙。所以威胁还得老老实实数0。

方法一、暴力隔离感染

+ 感染的方式算出每一块威胁需要多少墙，以及影响多少0。

+ 将威胁最大的一块变成2。

+ 重复上述操作。直到墙的数量不再增加。

方法一、暴力隔离感染

执行用时：134 ms, 在所有 Java 提交中击败了5.45%的用户

内存消耗：41.2 MB, 在所有 Java 提交中击败了5.45%的用户

通过测试用例：32 / 32
***/
public class Solution implements IDebug {

	int[][] isInfected;
	int m, n;
	int[] d = new int[] { 0, 1, 0, -1, -1, 0, 1, 0 };

	public int containVirus(int[][] isInfected) {
		this.isInfected = isInfected;
		this.m = isInfected.length;
		this.n = isInfected[0].length;
		int ans = 0;
		int wall = 0;
		do {
			if (wall != 0) {
				this.infect();
			}
			wall = this.maxWall();
			ans += wall;
		} while (wall != 0);
		return ans;
	}

	private int maxWall() {
		boolean[][] flag = new boolean[m][n];
		int maxm = -1, maxn = -1, wall = 0, refer = 0;
		for (int i = 0; i < m; i++) {
			for (int j = 0; j < n; j++) {
				boolean[][] refers = new boolean[m][n];
				int[] count = this.countWall(i, j, flag, refers);
				if (count[1] > refer) {
					refer = count[1];
					wall = count[0];
					maxm = i;
					maxn = j;
				}
			}
		}
		if (maxm != -1) {
			this.isolation(maxm, maxn);
		}
		return wall;
	}

	private void isolation(int x, int y) {
		this.isInfected[x][y] = 2;
		for (int i = 0; i < 8; i += 2) {
			int nextx = x + d[i], nexty = y + d[i + 1];
			if (nextx >= 0 && nextx < m && nexty >= 0 && nexty < n && this.isInfected[nextx][nexty] == 1) {
				this.isolation(nextx, nexty);
			}
		}
	}

	private int[] countWall(int x, int y, boolean[][] flag, boolean[][] refers) {
		int[] ans = new int[] { 0, 0 };
		if (flag[x][y] || this.isInfected[x][y] != 1) {
			return ans;
		}
		flag[x][y] = true;
		for (int i = 0; i < 8; i += 2) {
			int nextx = x + d[i], nexty = y + d[i + 1];
			if (nextx >= 0 && nextx < m && nexty >= 0 && nexty < n) {
				int next = this.isInfected[nextx][nexty];
				if (next == 0) {
					ans[0] += 1;
					if (!refers[nextx][nexty]) {
						refers[nextx][nexty] = true;
						ans[1] += 1;
					}
				} else if (next == 1) {
					int[] nextCount = this.countWall(nextx, nexty, flag, refers);
					ans[0] += nextCount[0];
					ans[1] += nextCount[1];
				}
			}
		}
		return ans;
	}

	private void infect() {
		boolean[][] flag = new boolean[m][n];
		for (int i = 0; i < m; i++) {
			for (int j = 0; j < n; j++) {
				this.spread(i, j, flag);
			}
		}
	}

	private void spread(int x, int y, boolean[][] flag) {
		if (this.isInfected[x][y] != 1 || flag[x][y]) {
			return;
		}
		flag[x][y] = true;
		for (int i = 0; i < 8; i += 2) {
			int nextx = x + d[i], nexty = y + d[i + 1];
			if (nextx >= 0 && nextx < m && nexty >= 0 && nexty < n) {
				int next = this.isInfected[nextx][nexty];
				if (next == 0) {
					flag[nextx][nexty] = true;
					this.isInfected[nextx][nexty] = 1;
				} else {
					this.spread(nextx, nexty, flag);
				}
			}
		}
	}

	@Override
	public void debug1() {
		HelpDebug.compare(10, this.containVirus(
				HelpDebug.str2array1("[[0,1,0,0,0,0,0,1],[0,1,0,0,0,0,0,1],[0,0,0,0,0,0,0,1],[0,0,0,0,0,0,0,0]]")));

	}

	@Override
	public void debug2() {
		// TODO Auto-generated method stub
		HelpDebug.compare(4, this.containVirus(HelpDebug.str2array1("[[1,1,1],[1,0,1],[1,1,1]]")));

	}

	@Override
	public void debug3() {
		// TODO Auto-generated method stub
		HelpDebug.compare(13, this.containVirus(HelpDebug.str2array1("[[1,1,1,0,0,0,0,0,0],[1,0,1,0,1,1,1,1,1],[1,1,1,0,0,0,0,0,0]]")));

	}

	@Override
	public void debug4() {
		// TODO Auto-generated method stub

		HelpDebug.compare(38, this.containVirus(HelpDebug.str2array1(
				"[[0,1,0,1,1,1,1,1,1,0],[0,0,0,1,0,0,0,0,0,0],[0,0,1,1,1,0,0,0,1,0],[0,0,0,1,1,0,0,1,1,0],[0,1,0,0,1,0,1,1,0,1],[0,0,0,1,0,1,0,1,1,1],[0,1,0,0,1,0,0,1,1,0],[0,1,0,1,0,0,0,1,1,0],[0,1,1,0,0,1,1,0,0,1],[1,0,1,1,0,1,0,1,0,1]]")));
	}

	public static void main(String[] args) {
		Solution so = new Solution();
		so.debug1();
		so.debug2();
		so.debug3();
		so.debug4();

	}

}
